package com.gitee.feizns.explore.data_structure.union_find;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

/**
 * 990. 等式方程的可满足性
 * @author feizns
 * @since 2020/3/13
 */
public class EquationsPossible {

    public static void main(String[] args) {
//        System.out.println(new EquationsPossible().equationsPossible(new String[]{"c==c", "f!=a", "f==b", "b==c"}));
    }

    public boolean equationsPossible(String[] equations) {
        Uf uf = new Uf();
        for (String equation : equations) {
            char[] sp = equation.toCharArray();
            char a = sp[0];
            char e = sp[1];
            char b = sp[3];
            uf.add(a);
            uf.add(b);
            if ( e == '=' )
                uf.union(a, b);
        }
        for (String equation : equations) {
            char[] sp = equation.toCharArray();
            char a = sp[0];
            char e = sp[1];
            char b = sp[3];
            if ( e == '=' && !uf.isConnected(a, b) )
                return false;
            else if ( e == '!' && uf.isConnected(a, b) )
                return false;
        }
        return true;
    }

    static class Uf {
        Map<Character, Character> PARENT = new HashMap<>();
        boolean contains(Character a) {
            return PARENT.containsKey(a);
        }
        void add(Character a) {
            if ( !contains(a) )
                PARENT.put(a, a);
        }
        void union(Character a, Character b) {
            add(a);
            add(b);
            Character ar = find(a);
            Character br = find(b);
            if ( !ar.equals(br) )
                PARENT.put(ar, br);
        }
        boolean isConnected(Character a, Character b) {
            Character ar = find(a);
            Character br = find(b);
            return ar != null && br != null && ar.equals(br);
        }
        Character find(Character a) {
            if ( contains(a) ) {
                Character p = PARENT.get(a);
                if ( a != p ) {
                    Character newP = find(p);
                    PARENT.put(a, newP);
                    return newP;
                }
                return p;
            }
            return null;
        }
    }

}
